#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int knightDialer(int n) {
        using LL = long long;
        const int MOD = 1e9 + 7;
        LL count_odd[10] = { 0 };
        LL count_even[10] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
        for (int i = 2; i <= n; i++)
        {
            if (i % 2 == 1)
            {
                count_even[0] = (count_odd[4] + count_odd[6]) % MOD;
                count_even[1] = (count_odd[6] + count_odd[8]) % MOD;
                count_even[2] = (count_odd[7] + count_odd[9]) % MOD;
                count_even[3] = (count_odd[4] + count_odd[8]) % MOD;
                count_even[4] = (count_odd[0] + count_odd[3] + count_odd[9]) % MOD;
                count_even[5] = 0;
                count_even[6] = (count_odd[0] + count_odd[1] + count_odd[7]) % MOD;
                count_even[7] = (count_odd[2] + count_odd[6]) % MOD;
                count_even[8] = (count_odd[1] + count_odd[3]) % MOD;
                count_even[9] = (count_odd[2] + count_odd[4]) % MOD;
            }
            else
            {
                count_odd[0] = (count_even[4] + count_even[6]) % MOD;
                count_odd[1] = (count_even[6] + count_even[8]) % MOD;
                count_odd[2] = (count_even[7] + count_even[9]) % MOD;
                count_odd[3] = (count_even[4] + count_even[8]) % MOD;
                count_odd[4] = (count_even[0] + count_even[3] + count_even[9]) % MOD;
                count_odd[5] = 0;
                count_odd[6] = (count_even[0] + count_even[1] + count_even[7]) % MOD;
                count_odd[7] = (count_even[2] + count_even[6]) % MOD;
                count_odd[8] = (count_even[1] + count_even[3]) % MOD;
                count_odd[9] = (count_even[2] + count_even[4]) % MOD;
            }
        }
        int res = 0;
        if (n % 2 == 0) for (auto num : count_odd) res = (res + num) % MOD;
        else for (auto num : count_even) res = (res + num) % MOD;
        return res;
    }
};